# Copyright (c) 2025, NVIDIA CORPORATION.  All rights reserved.
#
# NVIDIA CORPORATION and its licensors retain all intellectual property
# and proprietary rights in and to this software, related documentation
# and any modifications thereto.  Any use, reproduction, disclosure or
# distribution of this software and related documentation without an express
# license agreement from NVIDIA CORPORATION is strictly prohibited.

import torch

tri_table = torch.tensor([
    [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  3,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  9,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 1,  3,  8,  9,  1,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 4,  8,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 4,  0,  3,  7,  4,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  9,  1,  8,  7,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 4,  9,  1,  4,  1,  7,  7,  1,  3, -1, -1, -1, -1, -1, -1],
    [ 9,  4,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 9,  4,  5,  0,  3,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  4,  5,  1,  0,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 8,  4,  5,  8,  5,  3,  3,  5,  1, -1, -1, -1, -1, -1, -1],
    [ 9,  8,  7,  5,  9,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 9,  0,  3,  9,  3,  5,  5,  3,  7, -1, -1, -1, -1, -1, -1],
    [ 0,  8,  7,  0,  7,  1,  1,  7,  5, -1, -1, -1, -1, -1, -1],
    [ 1,  3,  5,  3,  7,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 3,  2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  2, 11,  8,  0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 1,  0,  9,  2, 11,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 1,  2, 11,  1, 11,  9,  9, 11,  8, -1, -1, -1, -1, -1, -1],
    [ 8,  7,  4,  3,  2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [11,  7,  4, 11,  4,  2,  2,  4,  0, -1, -1, -1, -1, -1, -1],
    [ 9,  1,  0,  8,  7,  4,  2, 11,  3, -1, -1, -1, -1, -1, -1],
    [ 4, 11,  7,  9, 11,  4,  9,  2, 11,  9,  1,  2, -1, -1, -1],
    [ 9,  4,  5,  2, 11,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  2, 11,  0, 11,  8,  4,  5,  9, -1, -1, -1, -1, -1, -1],
    [ 0,  4,  5,  0,  5,  1,  2, 11,  3, -1, -1, -1, -1, -1, -1],
    [ 2,  5,  1,  2,  8,  5,  2, 11,  8,  4,  5,  8, -1, -1, -1],
    [ 7,  5,  9,  7,  9,  8,  3,  2, 11, -1, -1, -1, -1, -1, -1],
    [ 9,  7,  5,  9,  2,  7,  9,  0,  2,  2, 11,  7, -1, -1, -1],
    [ 2, 11,  3,  0,  8,  1,  1,  8,  7,  1,  7,  5, -1, -1, -1],
    [11,  1,  2, 11,  7,  1,  7,  5,  1, -1, -1, -1, -1, -1, -1],
    [ 1, 10,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  3,  8,  1, 10,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 9, 10,  2,  0,  9,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 2,  3,  8,  2,  8, 10, 10,  8,  9, -1, -1, -1, -1, -1, -1],
    [ 1, 10,  2,  8,  7,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 3,  7,  4,  3,  4,  0,  1, 10,  2, -1, -1, -1, -1, -1, -1],
    [ 9, 10,  2,  9,  2,  0,  8,  7,  4, -1, -1, -1, -1, -1, -1],
    [ 2,  9, 10,  2,  7,  9,  2,  3,  7,  7,  4,  9, -1, -1, -1],
    [ 1, 10,  2,  9,  4,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 3,  8,  0,  1, 10,  2,  4,  5,  9, -1, -1, -1, -1, -1, -1],
    [ 5, 10,  2,  5,  2,  4,  4,  2,  0, -1, -1, -1, -1, -1, -1],
    [ 2,  5, 10,  3,  5,  2,  3,  4,  5,  3,  8,  4, -1, -1, -1],
    [ 9,  8,  7,  9,  7,  5, 10,  2,  1, -1, -1, -1, -1, -1, -1],
    [10,  2,  1,  9,  0,  5,  5,  0,  3,  5,  3,  7, -1, -1, -1],
    [ 8,  2,  0,  8,  5,  2,  8,  7,  5, 10,  2,  5, -1, -1, -1],
    [ 2,  5, 10,  2,  3,  5,  3,  7,  5, -1, -1, -1, -1, -1, -1],
    [ 3,  1, 10, 11,  3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  1, 10,  0, 10,  8,  8, 10, 11, -1, -1, -1, -1, -1, -1],
    [ 3,  0,  9,  3,  9, 11, 11,  9, 10, -1, -1, -1, -1, -1, -1],
    [ 9, 10,  8, 10, 11,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 3,  1, 10,  3, 10, 11,  7,  4,  8, -1, -1, -1, -1, -1, -1],
    [ 1, 10, 11,  1, 11,  4,  1,  4,  0,  7,  4, 11, -1, -1, -1],
    [ 4,  8,  7,  9, 11,  0,  9, 10, 11, 11,  3,  0, -1, -1, -1],
    [ 4, 11,  7,  4,  9, 11,  9, 10, 11, -1, -1, -1, -1, -1, -1],
    [10, 11,  3, 10,  3,  1,  9,  4,  5, -1, -1, -1, -1, -1, -1],
    [ 4,  5,  9,  0,  1,  8,  8,  1, 10,  8, 10, 11, -1, -1, -1],
    [ 5,  0,  4,  5, 11,  0,  5, 10, 11, 11,  3,  0, -1, -1, -1],
    [ 5,  8,  4,  5, 10,  8, 10, 11,  8, -1, -1, -1, -1, -1, -1],
    [ 9,  8,  5,  8,  7,  5, 10,  3,  1, 10, 11,  3, -1, -1, -1],
    [ 5,  0,  7,  5,  9,  0,  7,  0, 11,  1, 10,  0, 11,  0, 10],
    [11,  0, 10, 11,  3,  0, 10,  0,  5,  8,  7,  0,  5,  0,  7],
    [11,  5, 10,  7,  5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 7, 11,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 3,  8,  0, 11,  6,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  9,  1, 11,  6,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 8,  9,  1,  8,  1,  3, 11,  6,  7, -1, -1, -1, -1, -1, -1],
    [ 6,  4,  8, 11,  6,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 3, 11,  6,  3,  6,  0,  0,  6,  4, -1, -1, -1, -1, -1, -1],
    [ 8, 11,  6,  8,  6,  4,  9,  1,  0, -1, -1, -1, -1, -1, -1],
    [ 9,  6,  4,  9,  3,  6,  9,  1,  3, 11,  6,  3, -1, -1, -1],
    [ 4,  5,  9,  7, 11,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  3,  8,  4,  5,  9, 11,  6,  7, -1, -1, -1, -1, -1, -1],
    [ 5,  1,  0,  5,  0,  4,  7, 11,  6, -1, -1, -1, -1, -1, -1],
    [11,  6,  7,  8,  4,  3,  3,  4,  5,  3,  5,  1, -1, -1, -1],
    [ 6,  5,  9,  6,  9, 11, 11,  9,  8, -1, -1, -1, -1, -1, -1],
    [ 3, 11,  6,  0,  3,  6,  0,  6,  5,  0,  5,  9, -1, -1, -1],
    [ 0,  8, 11,  0, 11,  5,  0,  5,  1,  5, 11,  6, -1, -1, -1],
    [ 6,  3, 11,  6,  5,  3,  5,  1,  3, -1, -1, -1, -1, -1, -1],
    [ 7,  3,  2,  6,  7,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 7,  8,  0,  7,  0,  6,  6,  0,  2, -1, -1, -1, -1, -1, -1],
    [ 2,  6,  7,  2,  7,  3,  0,  9,  1, -1, -1, -1, -1, -1, -1],
    [ 1,  2,  6,  1,  6,  8,  1,  8,  9,  8,  6,  7, -1, -1, -1],
    [ 8,  3,  2,  8,  2,  4,  4,  2,  6, -1, -1, -1, -1, -1, -1],
    [ 0,  2,  4,  4,  2,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 1,  0,  9,  2,  4,  3,  2,  6,  4,  4,  8,  3, -1, -1, -1],
    [ 1,  4,  9,  1,  2,  4,  2,  6,  4, -1, -1, -1, -1, -1, -1],
    [ 7,  3,  2,  7,  2,  6,  5,  9,  4, -1, -1, -1, -1, -1, -1],
    [ 9,  4,  5,  0,  6,  8,  0,  2,  6,  6,  7,  8, -1, -1, -1],
    [ 3,  2,  6,  3,  6,  7,  1,  0,  5,  5,  0,  4, -1, -1, -1],
    [ 6,  8,  2,  6,  7,  8,  2,  8,  1,  4,  5,  8,  1,  8,  5],
    [ 5,  9,  8,  5,  8,  2,  5,  2,  6,  3,  2,  8, -1, -1, -1],
    [ 9,  6,  5,  9,  0,  6,  0,  2,  6, -1, -1, -1, -1, -1, -1],
    [ 1,  8,  5,  1,  0,  8,  5,  8,  6,  3,  2,  8,  6,  8,  2],
    [ 1,  6,  5,  2,  6,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [10,  2,  1,  6,  7, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 1, 10,  2,  3,  8,  0,  6,  7, 11, -1, -1, -1, -1, -1, -1],
    [ 2,  0,  9,  2,  9, 10,  6,  7, 11, -1, -1, -1, -1, -1, -1],
    [ 6,  7, 11,  2,  3, 10, 10,  3,  8, 10,  8,  9, -1, -1, -1],
    [ 6,  4,  8,  6,  8, 11,  2,  1, 10, -1, -1, -1, -1, -1, -1],
    [ 1, 10,  2,  3, 11,  0,  0, 11,  6,  0,  6,  4, -1, -1, -1],
    [ 4,  8, 11,  4, 11,  6,  0,  9,  2,  2,  9, 10, -1, -1, -1],
    [10,  3,  9, 10,  2,  3,  9,  3,  4, 11,  6,  3,  4,  3,  6],
    [ 9,  4,  5, 10,  2,  1,  7, 11,  6, -1, -1, -1, -1, -1, -1],
    [ 6,  7, 11,  1, 10,  2,  0,  3,  8,  4,  5,  9, -1, -1, -1],
    [ 7, 11,  6,  5, 10,  4,  4, 10,  2,  4,  2,  0, -1, -1, -1],
    [ 3,  8,  4,  3,  4,  5,  3,  5,  2, 10,  2,  5, 11,  6,  7],
    [ 1, 10,  2,  9, 11,  5,  9,  8, 11, 11,  6,  5, -1, -1, -1],
    [ 0,  3, 11,  0, 11,  6,  0,  6,  9,  5,  9,  6,  1, 10,  2],
    [11,  5,  8, 11,  6,  5,  8,  5,  0, 10,  2,  5,  0,  5,  2],
    [ 6,  3, 11,  6,  5,  3,  2,  3, 10, 10,  3,  5, -1, -1, -1],
    [10,  6,  7, 10,  7,  1,  1,  7,  3, -1, -1, -1, -1, -1, -1],
    [10,  6,  7,  1, 10,  7,  1,  7,  8,  1,  8,  0, -1, -1, -1],
    [ 0,  7,  3,  0, 10,  7,  0,  9, 10,  6,  7, 10, -1, -1, -1],
    [ 7, 10,  6,  7,  8, 10,  8,  9, 10, -1, -1, -1, -1, -1, -1],
    [ 8,  3,  1,  8,  1,  6,  8,  6,  4,  6,  1, 10, -1, -1, -1],
    [10,  0,  1, 10,  6,  0,  6,  4,  0, -1, -1, -1, -1, -1, -1],
    [ 4,  3,  6,  4,  8,  3,  6,  3, 10,  0,  9,  3, 10,  3,  9],
    [10,  4,  9,  6,  4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 9,  4,  5, 10,  6,  1,  1,  6,  7,  1,  7,  3, -1, -1, -1],
    [ 1, 10,  6,  1,  6,  7,  1,  7,  0,  8,  0,  7,  9,  4,  5],
    [ 4, 10,  0,  4,  5, 10,  0, 10,  3,  6,  7, 10,  3, 10,  7],
    [ 7, 10,  6,  7,  8, 10,  5, 10,  4,  4, 10,  8, -1, -1, -1],
    [ 1,  6,  3,  1, 10,  6,  3,  6,  8,  5,  9,  6,  8,  6,  9],
    [10,  0,  1, 10,  6,  0,  9,  0,  5,  5,  0,  6, -1, -1, -1],
    [ 0,  8,  3,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [10,  6,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [10,  5,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  3,  8,  5,  6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 9,  1,  0,  5,  6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 1,  3,  8,  1,  8,  9,  5,  6, 10, -1, -1, -1, -1, -1, -1],
    [ 5,  6, 10,  4,  8,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 4,  0,  3,  4,  3,  7,  6, 10,  5, -1, -1, -1, -1, -1, -1],
    [ 1,  0,  9,  5,  6, 10,  8,  7,  4, -1, -1, -1, -1, -1, -1],
    [10,  5,  6,  1,  7,  9,  1,  3,  7,  7,  4,  9, -1, -1, -1],
    [10,  9,  4,  6, 10,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 4,  6, 10,  4, 10,  9,  0,  3,  8, -1, -1, -1, -1, -1, -1],
    [10,  1,  0, 10,  0,  6,  6,  0,  4, -1, -1, -1, -1, -1, -1],
    [ 8,  1,  3,  8,  6,  1,  8,  4,  6,  6, 10,  1, -1, -1, -1],
    [ 7,  6, 10,  7, 10,  8,  8, 10,  9, -1, -1, -1, -1, -1, -1],
    [ 0,  3,  7,  0,  7, 10,  0, 10,  9,  6, 10,  7, -1, -1, -1],
    [10,  7,  6,  1,  7, 10,  1,  8,  7,  1,  0,  8, -1, -1, -1],
    [10,  7,  6, 10,  1,  7,  1,  3,  7, -1, -1, -1, -1, -1, -1],
    [ 2, 11,  3, 10,  5,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [11,  8,  0, 11,  0,  2, 10,  5,  6, -1, -1, -1, -1, -1, -1],
    [ 0,  9,  1,  2, 11,  3,  5,  6, 10, -1, -1, -1, -1, -1, -1],
    [ 5,  6, 10,  1,  2,  9,  9,  2, 11,  9, 11,  8, -1, -1, -1],
    [ 3,  2, 11,  7,  4,  8, 10,  5,  6, -1, -1, -1, -1, -1, -1],
    [ 5,  6, 10,  4,  2,  7,  4,  0,  2,  2, 11,  7, -1, -1, -1],
    [ 0,  9,  1,  4,  8,  7,  2, 11,  3,  5,  6, 10, -1, -1, -1],
    [ 9,  1,  2,  9,  2, 11,  9, 11,  4,  7,  4, 11,  5,  6, 10],
    [10,  9,  4, 10,  4,  6, 11,  3,  2, -1, -1, -1, -1, -1, -1],
    [ 0,  2,  8,  2, 11,  8,  4, 10,  9,  4,  6, 10, -1, -1, -1],
    [ 3,  2, 11,  0,  6,  1,  0,  4,  6,  6, 10,  1, -1, -1, -1],
    [ 6,  1,  4,  6, 10,  1,  4,  1,  8,  2, 11,  1,  8,  1, 11],
    [ 2, 11,  3, 10,  8,  6, 10,  9,  8,  8,  7,  6, -1, -1, -1],
    [ 2,  7,  0,  2, 11,  7,  0,  7,  9,  6, 10,  7,  9,  7, 10],
    [ 1,  0,  8,  1,  8,  7,  1,  7, 10,  6, 10,  7,  2, 11,  3],
    [11,  1,  2, 11,  7,  1, 10,  1,  6,  6,  1,  7, -1, -1, -1],
    [ 1,  5,  6,  2,  1,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 1,  5,  6,  1,  6,  2,  3,  8,  0, -1, -1, -1, -1, -1, -1],
    [ 9,  5,  6,  9,  6,  0,  0,  6,  2, -1, -1, -1, -1, -1, -1],
    [ 5,  8,  9,  5,  2,  8,  5,  6,  2,  3,  8,  2, -1, -1, -1],
    [ 6,  2,  1,  6,  1,  5,  4,  8,  7, -1, -1, -1, -1, -1, -1],
    [ 1,  5,  2,  5,  6,  2,  3,  4,  0,  3,  7,  4, -1, -1, -1],
    [ 8,  7,  4,  9,  5,  0,  0,  5,  6,  0,  6,  2, -1, -1, -1],
    [ 7,  9,  3,  7,  4,  9,  3,  9,  2,  5,  6,  9,  2,  9,  6],
    [ 1,  9,  4,  1,  4,  2,  2,  4,  6, -1, -1, -1, -1, -1, -1],
    [ 3,  8,  0,  1,  9,  2,  2,  9,  4,  2,  4,  6, -1, -1, -1],
    [ 0,  4,  2,  4,  6,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 8,  2,  3,  8,  4,  2,  4,  6,  2, -1, -1, -1, -1, -1, -1],
    [ 1,  6,  2,  1,  8,  6,  1,  9,  8,  8,  7,  6, -1, -1, -1],
    [ 2,  9,  6,  2,  1,  9,  6,  9,  7,  0,  3,  9,  7,  9,  3],
    [ 7,  0,  8,  7,  6,  0,  6,  2,  0, -1, -1, -1, -1, -1, -1],
    [ 7,  2,  3,  6,  2,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 6, 11,  3,  6,  3,  5,  5,  3,  1, -1, -1, -1, -1, -1, -1],
    [ 0, 11,  8,  0,  5, 11,  0,  1,  5,  5,  6, 11, -1, -1, -1],
    [ 3,  6, 11,  0,  6,  3,  0,  5,  6,  0,  9,  5, -1, -1, -1],
    [ 6,  9,  5,  6, 11,  9, 11,  8,  9, -1, -1, -1, -1, -1, -1],
    [ 8,  7,  4,  3,  5, 11,  3,  1,  5,  5,  6, 11, -1, -1, -1],
    [ 5, 11,  1,  5,  6, 11,  1, 11,  0,  7,  4, 11,  0, 11,  4],
    [ 0,  9,  5,  0,  5,  6,  0,  6,  3, 11,  3,  6,  8,  7,  4],
    [ 6,  9,  5,  6, 11,  9,  4,  9,  7,  7,  9, 11, -1, -1, -1],
    [ 9,  4,  6,  9,  6,  3,  9,  3,  1, 11,  3,  6, -1, -1, -1],
    [ 8,  1, 11,  8,  0,  1, 11,  1,  6,  9,  4,  1,  6,  1,  4],
    [ 3,  6, 11,  3,  0,  6,  0,  4,  6, -1, -1, -1, -1, -1, -1],
    [ 6,  8,  4, 11,  8,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 8,  6,  9,  8,  7,  6,  9,  6,  1, 11,  3,  6,  1,  6,  3],
    [ 0,  1,  9, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 7,  0,  8,  7,  6,  0,  3,  0, 11, 11,  0,  6, -1, -1, -1],
    [ 7,  6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [11, 10,  5,  7, 11,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [11, 10,  5, 11,  5,  7,  8,  0,  3, -1, -1, -1, -1, -1, -1],
    [ 5,  7, 11,  5, 11, 10,  1,  0,  9, -1, -1, -1, -1, -1, -1],
    [10,  5,  7, 10,  7, 11,  9,  1,  8,  8,  1,  3, -1, -1, -1],
    [ 5,  4,  8,  5,  8, 10, 10,  8, 11, -1, -1, -1, -1, -1, -1],
    [ 5,  4,  0,  5,  0, 11,  5, 11, 10, 11,  0,  3, -1, -1, -1],
    [ 0,  9,  1,  8, 10,  4,  8, 11, 10, 10,  5,  4, -1, -1, -1],
    [10,  4, 11, 10,  5,  4, 11,  4,  3,  9,  1,  4,  3,  4,  1],
    [ 4,  7, 11,  4, 11,  9,  9, 11, 10, -1, -1, -1, -1, -1, -1],
    [ 0,  3,  8,  4,  7,  9,  9,  7, 11,  9, 11, 10, -1, -1, -1],
    [ 1, 11, 10,  1,  4, 11,  1,  0,  4,  7, 11,  4, -1, -1, -1],
    [ 3,  4,  1,  3,  8,  4,  1,  4, 10,  7, 11,  4, 10,  4, 11],
    [ 9,  8, 10, 10,  8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 3,  9,  0,  3, 11,  9, 11, 10,  9, -1, -1, -1, -1, -1, -1],
    [ 0, 10,  1,  0,  8, 10,  8, 11, 10, -1, -1, -1, -1, -1, -1],
    [ 3, 10,  1, 11, 10,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 2, 10,  5,  2,  5,  3,  3,  5,  7, -1, -1, -1, -1, -1, -1],
    [ 8,  0,  2,  8,  2,  5,  8,  5,  7, 10,  5,  2, -1, -1, -1],
    [ 9,  1,  0,  5,  3, 10,  5,  7,  3,  3,  2, 10, -1, -1, -1],
    [ 9,  2,  8,  9,  1,  2,  8,  2,  7, 10,  5,  2,  7,  2,  5],
    [ 2, 10,  5,  3,  2,  5,  3,  5,  4,  3,  4,  8, -1, -1, -1],
    [ 5,  2, 10,  5,  4,  2,  4,  0,  2, -1, -1, -1, -1, -1, -1],
    [ 3,  2, 10,  3, 10,  5,  3,  5,  8,  4,  8,  5,  0,  9,  1],
    [ 5,  2, 10,  5,  4,  2,  1,  2,  9,  9,  2,  4, -1, -1, -1],
    [ 2, 10,  9,  2,  9,  7,  2,  7,  3,  7,  9,  4, -1, -1, -1],
    [ 9,  7, 10,  9,  4,  7, 10,  7,  2,  8,  0,  7,  2,  7,  0],
    [ 3, 10,  7,  3,  2, 10,  7, 10,  4,  1,  0, 10,  4, 10,  0],
    [ 1,  2, 10,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 2,  8,  3,  2, 10,  8, 10,  9,  8, -1, -1, -1, -1, -1, -1],
    [ 9,  2, 10,  0,  2,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 2,  8,  3,  2, 10,  8,  0,  8,  1,  1,  8, 10, -1, -1, -1],
    [ 1,  2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [11,  2,  1, 11,  1,  7,  7,  1,  5, -1, -1, -1, -1, -1, -1],
    [ 0,  3,  8,  1,  7,  2,  1,  5,  7,  7, 11,  2, -1, -1, -1],
    [ 9,  5,  7,  9,  7,  2,  9,  2,  0,  2,  7, 11, -1, -1, -1],
    [ 7,  2,  5,  7, 11,  2,  5,  2,  9,  3,  8,  2,  9,  2,  8],
    [ 2,  1,  5,  2,  5,  8,  2,  8, 11,  4,  8,  5, -1, -1, -1],
    [ 0, 11,  4,  0,  3, 11,  4, 11,  5,  2,  1, 11,  5, 11,  1],
    [ 0,  5,  2,  0,  9,  5,  2,  5, 11,  4,  8,  5, 11,  5,  8],
    [ 9,  5,  4,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 4,  7, 11,  9,  4, 11,  9, 11,  2,  9,  2,  1, -1, -1, -1],
    [ 9,  4,  7,  9,  7, 11,  9, 11,  1,  2,  1, 11,  0,  3,  8],
    [11,  4,  7, 11,  2,  4,  2,  0,  4, -1, -1, -1, -1, -1, -1],
    [11,  4,  7, 11,  2,  4,  8,  4,  3,  3,  4,  2, -1, -1, -1],
    [ 1, 11,  2,  1,  9, 11,  9,  8, 11, -1, -1, -1, -1, -1, -1],
    [ 3,  9,  0,  3, 11,  9,  1,  9,  2,  2,  9, 11, -1, -1, -1],
    [ 0, 11,  2,  8, 11,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 3, 11,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 1,  5,  3,  3,  5,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  7,  8,  0,  1,  7,  1,  5,  7, -1, -1, -1, -1, -1, -1],
    [ 9,  3,  0,  9,  5,  3,  5,  7,  3, -1, -1, -1, -1, -1, -1],
    [ 9,  7,  8,  5,  7,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 8,  5,  4,  8,  3,  5,  3,  1,  5, -1, -1, -1, -1, -1, -1],
    [ 0,  5,  4,  1,  5,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 8,  5,  4,  8,  3,  5,  9,  5,  0,  0,  5,  3, -1, -1, -1],
    [ 9,  5,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 4,  1,  9,  4,  7,  1,  7,  3,  1, -1, -1, -1, -1, -1, -1],
    [ 4,  1,  9,  4,  7,  1,  0,  1,  8,  8,  1,  7, -1, -1, -1],
    [ 4,  3,  0,  7,  3,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 4,  7,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 1,  8,  3,  9,  8,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  1,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  8,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
], dtype=torch.long, device="cuda")


def vert_interp(iso, p1, p2, v1, v2):
    r = (iso - v1) / (v2 - v1)
    r[(v1 - v2).abs() < 1e-9] = 0.5
    p_interp = (p1 + r.unsqueeze(1) * (p2 - p1))
    return p_interp


def torch_marching_cubes_grid(grid_pts_val, grid_pts_xyz, vox_key, iso, chunk_sz=10_000_000):
    '''
    Marching cubes given voxel values on their eight grid points.
    Input:
        @grid_pts_val    [n_pt]      The sign distance values of the grid points.
        @grid_pts_xyz    [n_pt, 3]   The xyz coordinates of the grid points.
        @vox_key         [n_vox, 8]  Indices to the eight grid points of each voxel.
        @iso             float       Iso value of the level set.
    Output:
        @verts           [n_vert, 3] The vertices of the mesh.
        @faces           [n_face, 3] The indices to the vert of each face.
    '''
    # Gather unit voxel parameters
    vlst = []
    flst = []
    n_prefix_v = 0
    for key in vox_key.split(chunk_sz):
        unit_val = grid_pts_val[key].reshape(len(key), 8)
        unit_xyz = grid_pts_xyz[key]
        v, f = torch_marching_cubes_voxels(unit_val, unit_xyz, iso)
        vlst.append(v)
        flst.append(f + n_prefix_v)
        n_prefix_v += len(v)

    if len(vlst) == 1:
        return vlst[0], flst[0]

    # Merge duplicated vertices and remap vert index of mesh faces
    vlst = torch.cat(vlst)
    flst = torch.cat(flst)
    faces_xyz = vlst[flst]
    faces_xyz = faces_xyz.reshape(-1, 3)  # [n, 3, 3] => [n*3, 3]
    mesh_verts, mesh_faces = faces_xyz.unique(dim=0, return_inverse=True)
    mesh_faces = mesh_faces.reshape(-1, 3)
    return mesh_verts, mesh_faces


def torch_marching_cubes_voxels(unit_val, unit_xyz, iso):
    '''
    Marching cubes given voxel values on their eight grid points.
    Input:
        @unit_val    [n_vox, 8]     The sign distance values of the eight grid points.
        @unit_xyz    [n_vox, 8, 3]  The xyz coordinates of the eight grid points.
        @iso         float          Iso value of the level set.
    Output:
        @verts       [n_vert, 3]    The vertices of the mesh.
        @faces       [n_face, 3]    The indices to the vert of each face.
    '''
    # Filter voxels w/o the target level set
    mask = (unit_val > iso).any(1) & (unit_val < iso).any(1) & ~unit_val.isnan().any(1)
    filter_idx = torch.where(mask)[0]
    unit_val = unit_val[filter_idx]
    unit_xyz = unit_xyz[filter_idx]
    n_vox = len(unit_val)
    del mask, filter_idx
    torch.cuda.empty_cache()

    # Compute intersection of the level set and the voxel edge
    pair_lst = [
        [0, 1],
        [1, 5],
        [5, 4],
        [4, 0],
        [2, 3],
        [3, 7],
        [7, 6],
        [6, 2],
        [0, 2],
        [1, 3],
        [5, 7],
        [4, 6],
    ]
    unit_val_lst = [v for v in unit_val.moveaxis(1 ,0)]
    unit_xyz_lst = [v for v in unit_xyz.moveaxis(1 ,0)]
    vert_lst = []
    for i in range(12):
        a, b = pair_lst[i]
        vert = vert_interp(iso, unit_xyz_lst[a], unit_xyz_lst[b], unit_val_lst[a], unit_val_lst[b])
        vert_lst.append(vert)
    vert_lst = torch.stack(vert_lst, dim=1)  # [n_vox, 12, 3]
    del unit_val_lst, unit_xyz_lst
    torch.cuda.empty_cache()

    # Determine cases
    bases = 1 << torch.arange(8, dtype=torch.long, device="cuda")
    cube_idx = ((unit_val < iso) * bases).sum(1)

    # Create triangle
    tri_idx = tri_table[cube_idx]
    faces_xyz = vert_lst[
        torch.arange(n_vox, device="cuda").unsqueeze(1),
        tri_idx]
    del vert_lst, cube_idx
    torch.cuda.empty_cache()

    # Remove dummy
    faces_xyz = faces_xyz[tri_idx != -1]  # [n_faces * 3, 3]
    assert len(faces_xyz) % 3 == 0, "Sanity failed!? Please double check tri_table."

    # Merge duplicated vertices and remap vert index of mesh faces
    mesh_verts, mesh_faces = faces_xyz.unique(dim=0, return_inverse=True)
    mesh_faces = mesh_faces.reshape(-1, 3)
    return mesh_verts, mesh_faces
